package com.lxw.question;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class MaxQueue {
    /**
     * 题目描述
     * 请定义一个队列并实现函数 max_value 得到队列里的最大值，
     * 要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
     *
     * 若队列为空，pop_front 和 max_value 需要返回 -1
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof
     */

    /**
     * 解题思路
     * 维护一个正常的队列（使用ArrayList)来完成添加和删除的操作
     * 维护一个具有可以获悉当前队列中最大元素的值得队列（对队列进行排序）。
     * 当往正常的队列中添加元素时，同时往另一个队列中添加元素，并进行排序。
     */
    //正常队列的数组
    private ArrayList<Integer> queue;
    //单调队列的数组
    private ArrayList<Integer> dequeue;

    private int endIndex = 0;
    private int headIndex = 0;

    public MaxQueue() {
        //数组的默认大小为50，后期可能需要进行扩容
        queue = new ArrayList<>();
        dequeue = new ArrayList<>();
    }

    public int max_value() {
        return getMaxFromDull();
    }

    public void push_back(int value) {
        queue.add(endIndex,value);
        System.out.println("添加"+value+"向queue中");
        endIndex++;

        push_dull(value);
    }

    /**
     * 整理单调队列的值
     * @return
     */
    public void push_dull(int value){
        dequeue.add(value);
        System.out.println("添加"+value+"向dequeue");
        Collections.sort(dequeue);
    }


    private int getMaxFromDull(){
        if(dequeue.size() != 0){
            return dequeue.get(dequeue.size() - 1);
        }
        return -1;

    }

    public int pop_front() {
        if(queue.size() == 0){
            return -1;
        }
        endIndex--;
        int ret = queue.get(0);
        queue.remove(0);

        int i = dequeue.lastIndexOf(ret);
        dequeue.remove(i);
        return ret;
    }

    public void shuchu(){
        System.out.println("queue:"+queue);
        System.out.println(dequeue);
    }

}
